package com.jia.interviewPro;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: Leetcode
 * @description:  https://leetcode-cn.com/problems/find-majority-element-lcci/
 * @author: STU756
 * @create: 2020-09-03 14:18
 */
public class Pro1710 {
    //5.分治
    public int majorityElement(int[] array) {
        int result = divide(array, 0, array.length - 1);
        return checkMoreThanHalf(array, result)? result : -1;
    }
    private int divide(int[] array, int st, int ed) {
        if(st == ed) {
            return array[st]; }
        else {
            int mid = st + ((ed - st) >> 1);
            int leftMajority = divide(array, st, mid);
            int rightMajority = divide(array, mid + 1, ed);
            int countleftMajority = countMajority(array, st, mid, leftMajority);
            int countRightMajority = countMajority(array, mid + 1, ed ,rightMajority);
            return countleftMajority > countRightMajority? leftMajority : rightMajority;
        }
    }
    private int countMajority(int[] array, int st, int ed, int num) {
        int count = 0;
        for(int i = st; i <=ed ; i++) {
            if(num == array[i]) {
                ++count;
            }
        }
        return count;
    }


    //4.位运算    Integer  32bit，每个位1个数大于一半，加入结果中
    public int majorityElement5(int[] array) {
        int ans = 0;
        int index = 1;
        int countOne = 0;
        for(int i = 0; i < 32; i++) {
            index = 1<<i;
            countOne = 0;
            for(int num : array) {
                if((num & index)!=0) {
                    countOne++;
                }
            }
            if(countOne > array.length / 2) {
                ans |= index;
            }
        }
        return checkMoreThanHalf(array, ans)? ans : -1;
    }

    //3.计数
    public int majorityElement3(int[] array) {
        HashMap<Integer,Integer> map = new HashMap<>();//<num,count>
        for(int num : array) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int len = array.length / 2;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if(entry.getValue() > len) {
                return entry.getKey();
            }
        }
        return -1;
    }
    //2.摩尔投票
    public int majorityElement2(int[] array) {
        int major = 0, count = 0;
        for(int n : array) {
            if(count == 0) {
                ++count;
                major = n;
            }else {
                if(major == n) {
                    ++count;
                }else {
                    --count;
                }
            }
        }
        return checkMoreThanHalf(array,major)? major : -1;
    }

    /**
     * 1.使用快排中的partition找出中位数，再利用中位数进行统计是否符合要求超过一半的数
     */

    public int majorityElement1(int[] array) {
        if (array == null || array.length == 0)
            return 0;
        int result = partition(array, 0, array.length - 1);
        if (checkMoreThanHalf(array, result)) {
            return result;
        }
        return 0;
    }

    private boolean checkMoreThanHalf(int[] array, int result) {
        int len = array.length;
        int count = 0;
        for (int val : array) {
            if (result == val) {
                ++count;
            }
            if (count > len / 2)
                return true;
        }
        return false;
    }

    private int partition(int[] array, int start, int end) {
        /*** 快排partition函数原代码——start ***/
        int left = start;
        int right = end;

        int p = array[start];
        while (left < right) {
            while (left < right && array[right] >= p) right--;
            ;
            if (left < right)
                array[left++] = array[right];
            while (left < right && array[left] <= p) left++;
            ;
            if (left < right)
                array[right--] = array[left];
        }
        array[left] = p;

        /*** 定位判断 ***/
        if (left == array.length / 2) {
            return array[left];
        } else if (left > array.length / 2) {
            return partition(array, start, left - 1);
        } else {
            return partition(array, left + 1, end);
        }
    }
}
